package com.lc.projects.structure.heap;

import java.util.Arrays;

/**
 * 随手写，堆排序
 * 
 * @author LC
 *
 */
public class MaxHeapArray {
	public static void main(String[] args) {
		MaHeap heap = new MaHeap(10);
		heap.insert(9);
		heap.insert(5);
		heap.insert(6);
		heap.insert(3);
		heap.insert(8);
		heap.insert(2);
		heap.insert(35);
		heap.insert(21);
		heap.insert(2);
		heap.insert(15);
		System.out.println(heap);

		while (heap.getTop() != null) {
			System.out.print(heap.getTop() + " ");
			heap.deleteTop();
		}
	}
}

class MaHeap {

	private int[] data;
	private int cursor = -1;

	public MaHeap(int size) {
		if (size > 0) {
			data = new int[size];
			cursor = -1;
		} else {
			System.out.println("Size can not be less than 1.");
		}
	}

	public boolean isFull() {
		return cursor == data.length - 1;
	}

	public void insert(int value) {
		if (!isFull()) {
			cursor += 1;
			data[cursor] = value;
			shiftUp(cursor);
		} else {
			System.out.println("Full. Element not input :" + value);
		}
	}

	private void shiftUp(int index) {
		while (index != 0) {
			int now = data[index];
			int parent = data[(index - 1) / 2];
			if (now > parent) {
				data[index] = parent;
				data[(index - 1) / 2] = now;
				index = (index - 1) / 2;
			} else {
				break;
			}
		}
	}

	private void shiftDown(int index) {
		while (index < cursor) {
			int now = data[index];

			if (index * 2 + 2 <= cursor) {
				int son1 = data[index * 2 + 1];
				int son2 = data[index * 2 + 2];

				if (now > son1 && now > son2) {
					break;
				} else if (son1 > son2) {
					data[index] = son1;
					data[index * 2 + 1] = now;
					index = index * 2 + 1;
				} else {
					data[index] = son2;
					data[index * 2 + 2] = now;
					index = index * 2 + 2;
				}
			} else if (index * 2 + 1 >= cursor) {
				break;
			} else {
				int son1 = data[index * 2 + 1];

				if (now > son1) {
					break;
				} else {
					data[index] = son1;
					data[index * 2 + 1] = now;
					index = index * 2 + 1;
				}
			}

		}
	}

	public void deleteTop() {
		if (cursor > -1) {
			data[0] = data[cursor];
			data[cursor] = -1;
			cursor -= 1;
			shiftDown(0);
		} else {
			System.out.println("No Element.");
		}
	}

	public Integer getTop() {
		if (cursor > -1) {
			return data[0];
		} else {
			return null;
		}
	}

	@Override
	public String toString() {
		return "MaxHeap [data=" + Arrays.toString(data) + "]";
	}

}